
元组是基本的异构容器，有必要考虑如何在运行时(存储、执行时)和编译时(模板实例化数量)优化元组的使用。本节讨论对Tuple实现的一些特定优化。

\subsubsubsection{25.5.1\hspace{0.2cm}元组和EBCO}

元组存储公式使用了更多的存储空间。一个问题是尾部成员最终将是一个空元组，每个非空元组都以一个空元组结束，而且数据成员必须始终有至少一个字节的存储空间。

为了提高元组的存储效率，可以通过继承尾元组而不是使其成为成员来应用21.1节中讨论的空基类优化(EBCO):

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/tuplestorage1.hpp}
\begin{lstlisting}[style=styleCXX]
// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...> : private Tuple<Tail...>
{
	private:
	Head head;
	public:
	Head& getHead() { return head; }
	Head const& getHead() const { return head; }
	Tuple<Tail...>& getTail() { return *this; }
	Tuple<Tail...> const& getTail() const { return *this; }
};
\end{lstlisting}

这与我们在第21.1.2节中使用的BaseMemberPair方法相同。但有一个副作用，即会在构造函数中颠倒元组元素初始化的顺序。以前，因为头部成员位于尾部成员之前，所以会先初始化头部成员。这种新的元组存储方式中，尾部位于基类中，因此将在成员头部之前初始化。

\begin{tcolorbox}[colback=webgreen!5!white,colframe=webgreen!75!black]
\hspace*{0.75cm}此更改的另一个影响是，因为基类通常存储在成员之前，所以元组的元素最终将以相反的顺序存储。
\end{tcolorbox}

这个问题可以通过将头部成员嵌入到基类列表中，位于尾部之前的基类来解决。直接实现将引入一个TupleElt模板，用于封装每个元素类型，以便Tuple可以继承:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/tuplestorage2.hpp}
\begin{lstlisting}[style=styleCXX]
template<typename... Types>
class Tuple;

template<typename T>
class TupleElt
{
	T value;
	
	public:
	TupleElt() = default;
	template<typename U>
	TupleElt(U&& other) : value(std::forward<U>(other) { }
	
	T& get() { return value; }
	T const& get() const { return value; }
};

// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...>
: private TupleElt<Head>, private Tuple<Tail...>
{
	public:
	Head& getHead() {
		// potentially ambiguous
		return static_cast<TupleElt<Head> *>(this)->get();
	}
	Head const& getHead() const {
		// potentially ambiguous
		return static_cast<TupleElt<Head> const*>(this)->get();
	}
	Tuple<Tail...>& getTail() { return *this; }
	Tuple<Tail...> const& getTail() const { return *this; }
};

// basis case:
template<>
class Tuple<> {
	// no storage required
};
\end{lstlisting}

虽然这种方法解决了初始化排序问题，但也引入了一个新的(更糟糕的)问题:不能再从具有两个相同类型元素的元组中提取元素，例如tuple<int, int>，从元组到该类型的元组的派生到基的转换(例如TupleElt<int>)将有歧义。

为了打破这种模糊性，需要确保每个TupleElt基类在给定的Tuple中唯一。一种方法是在其元组中编码该值的“高度”，即尾元组的长度。元组中最后一个元素的高度为0，倒数第二个元素的高度为1，依此类推:

\begin{tcolorbox}[colback=webgreen!5!white,colframe=webgreen!75!black]
\hspace*{0.75cm}更直观的做法是简单地使用元组元素的索引，而不是高度。因为给定的元组既可能作为独立元组出现，也可能作为另一个元组的尾部出现，所以这些信息在元组中并不容易获得。然而，给定的元组确实知道自己的尾部有多少元素。
\end{tcolorbox}

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/tupleelt1.hpp}
\begin{lstlisting}[style=styleCXX]
template<unsigned Height, typename T>
class TupleElt {
	T value;
	public:
	TupleElt() = default;
	
	template<typename U>
	TupleElt(U&& other) : value(std::forward<U>(other)) { }
	
	T& get() { return value; }
	T const& get() const { return value; }
};
\end{lstlisting}

通过这个解决方案，可以产生一个Tuple，其使用EBCO，同时保持初始化顺序，并支持同一类型的多个元素:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/tuplestorage3.hpp}
\begin{lstlisting}[style=styleCXX]
template<typename... Types>
class Tuple;

// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...>
: private TupleElt<sizeof...(Tail), Head>, private Tuple<Tail...>
{
	using HeadElt = TupleElt<sizeof...(Tail), Head>;
	public:
	Head& getHead() {
		return static_cast<HeadElt *>(this)->get();
	}
	Head const& getHead() const {
		return static_cast<HeadElt const*>(this)->get();
	}
	Tuple<Tail...>& getTail() { return *this; }
	Tuple<Tail...> const& getTail() const { return *this; }
};

// basis case:
template<>
class Tuple<> {
	// no storage required
};
\end{lstlisting}

有了这个实现，再看看下面的程序:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/compressedtuple1.cpp}
\begin{lstlisting}[style=styleCXX]
#include <algorithm>
#include "tupleelt1.hpp"
#include "tuplestorage3.hpp"
#include <iostream>

struct A {
	A() {
		std::cout << "A()" << ’\n’;
	}
};

struct B {
	B() {
		std::cout << "B()" << ’\n’;
	}
};

int main()
{
	Tuple<A, char, A, char, B> t1;
	std::cout << sizeof(t1) << " bytes" << ’\n’;
}
\end{lstlisting}

输出为

\begin{lstlisting}[style=styleCXX]
A()
A()
B()
5 bytes
\end{lstlisting}

EBCO删除了一个字节(对于空元组Tuple<>)。但A和B都是空类，这意味着在Tuple中有更多的机会使用EBCO。TupleElt可以进行扩展，在安全的情况下继承元素类型，不需要更改Tuple:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/tupleelt2.hpp}
\begin{lstlisting}[style=styleCXX]
#include <type_traits>

template<unsigned Height, typename T,
		bool = std::is_class<T>::value && !std::is_final<T>::value>
class TupleElt;

template<unsigned Height, typename T>
class TupleElt<Height, T, false>
{
	T value;
	
	public:
	TupleElt() = default;
	template<typename U>
		TupleElt(U&& other) : value(std::forward<U>(other)) { }
		
	T& get() { return value; }
	T const& get() const { return value; }
};

template<unsigned Height, typename T>
class TupleElt<Height, T, true> : private T
{
	public:
	TupleElt() = default;
	template<typename U>
		TupleElt(U&& other) : T(std::forward<U>(other)) { }
		
	T& get() { return *this; }
	T const& get() const { return *this; }
};
\end{lstlisting}

当TupleElt是一个非final类时，会私有地继承该类，以允许EBCO可以用于存储值。有了这个修改，程序现在的输出为

\begin{lstlisting}[style=styleCXX]
A()
A()
B()
2 bytes
\end{lstlisting}

\subsubsubsection{25.5.2\hspace{0.2cm}常量时间的get()}

使用元组时，get()操作非常常见，但它的递归实现需要线性数量的模板实例化，这会影响编译时间。在上一节介绍的EBCO优化已经实现了更有效的get实现，我们将在这里进行描述。

关键的理解是模板参数推导(第15章)，当形参(基类类型)与实参(派生类类型)匹配时，需要推导基类的模板实参。若可以计算想要提取的元素的高度H，就可以靠从Tuple特化到TupleElt<H, T>(其中T需要进行推导)的转换来提取，而无需遍历所有索引:

\hspace*{\fill} \\ %插入空行
\noindent
\textit{tuples/constantget.hpp}
\begin{lstlisting}[style=styleCXX]
template<unsigned H, typename T>
T& getHeight(TupleElt<H,T>& te)
{
	return te.get();
}

template<typename... Types>
class Tuple;

template<unsigned I, typename... Elements>
auto get(Tuple<Elements...>& t)
	-> decltype(getHeight<sizeof...(Elements)-I-1>(t))
{
	return getHeight<sizeof...(Elements)-I-1>(t);
}
\end{lstlisting}

因为get<I>(t)接收所需元素的索引I(从元组的开始计数)，而元组的实际存储是根据高度H(从元组的结束计数)计算的，所以可以通过I计算H。调用getHeight()的模板参数推导执行实际的搜索:高度H是固定的，因为可以在调用中显式地提供，所以只有一个TupleElt基类匹配，从而可以推导出类型T。注意，必须将getHeight()声明为Tuple的友元，从而允许转换为私有基类。例如:

\begin{lstlisting}[style=styleCXX]
// inside the recursive case for class template Tuple:
template<unsigned I, typename... Elements>
friend auto get(Tuple<Elements...>& t)
	-> decltype(getHeight<sizeof...(Elements)-I-1>(t));
\end{lstlisting}

因为已经将复杂的索引匹配工作转移到编译器模板推导那里，所以这里的实现方式只需要常数数量的模板实例化。









